package real.unknown.array;
import java.util.*;

// import jdk.javadoc.internal.tool.Main;
public class CompileArray {
   


   static class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         * 编译顺序
         * @param input string字符串 
         * @return string字符串
         * 
         *  for (int i = 0; i < len; i++) {
                dic[i] = i;
            }
            if (cur.size() < len) {
                for (int i = 0; i < len; i++) {
                    if (!cur.contains(dic[i])) {
                        res.append(dic[i] + ",");
                        cur.add(dic[i]);
                    }
                }
            }
         * 
         * 
         * 一个完整的软件项目往往会包含很多由代码和文档组成的源文件。编译器在编译整个项目的时候，
         * 可能需要按照依赖关系来依次编译每个源文件。比如，A.cpp 依赖 B.cpp，那么在编译的时候，
         * 编译器需要先编译 B.cpp，才能再编译 A.cpp。 假设现有 0，1，2，3 四个文件，
         * 0号文件依赖1号文件，1号文件依赖2号文件，3号文件依赖1号文件，则源文件的编译顺序为 2,1,0,3 或 2,1,3,0。
         * 现给出文件依赖关系，如 1,2,-1,1，表示0号文件依赖1号文件，1号文件依赖2号文件，2号文件没有依赖，
         * 3号文件依赖1号文件。请补充完整程序，返回正确的编译顺序。注意如有同时可以编译多个文件的情况，
         * 按数字升序返回一种情况即可，比如前述案例输出为：2,1,0,3
            输入例子1:
            "1,2,-1,1"

            输出例子1:
            "2,1,0,3"
         */
        public String compileSeq2 (String input) {

            input = input.replace(" ", ""); //去除所有空格
            int[] nums = Arrays.stream(input.split(",")).mapToInt(Integer:: parseInt).toArray();
            int num = nums.length;
            int[] inDgree = new int[num];
            Map<Integer, List<Integer>> adj = new HashMap<>();

            for (int i = 0; i < num; i++) {
                int idx; //s.charAt(i)表示： i文件的前置是idx
                if ((idx = nums[i]) > 0) {
                    //下标对应的指向为正数，证明是存在前置节点的
                    inDgree[i]++; //存在前置，因此入度加一

                    //根据前置、后置关系更新邻接表
                    if (adj.containsKey(idx)) {
                        List<Integer> list = adj.get(idx);
                        list.add(i);
                        adj.put(idx, list);
                    } else {
                        List<Integer> list = new ArrayList<>();
                        list.add(i);
                        adj.put(idx, list);
                    }
                }
            }

            System.out.println(Arrays.toString(inDgree));
            System.out.println(adj);

            Queue<Integer> queue = new LinkedList<>();
            
            StringBuilder sb = new StringBuilder();

            //将所有入度为零的节点加入队列
            for (int i = 0; i < num; i++) {
                if (inDgree[i] == 0) {
                    queue.offer(i);

                    //加入这些为0的为首先编译的对象
                    sb.append(i);
                }
            }

            // int count = 0;
            while (!queue.isEmpty()) {
                int p = queue.poll();
                //本题的逻辑是找到序列， 无需做额外的遍历，只需要按顺序收集那些入度为零的节点即可

                List<Integer> posts = adj.get(p);
                if (posts == null) continue;
                for (int post: posts) {
                    inDgree[post]--;
                    if (inDgree[post] == 0) {
                        queue.offer(post);
                        //时刻记得本题的目标
                        sb.append(post);
                    }
                }
            }
            return sb.toString();
        }

        //通过深度遍历实现
        int[] flag;
        Map<Integer, List<Integer>> adj;
        StringBuilder sb; //记录最终结果
        public String compileSeq (String input) {
            input = input.replace(" ", ""); //去除所有空格
            int[] nums = Arrays.stream(input.split(",")).mapToInt(Integer:: parseInt).toArray();
            int num = nums.length;
            adj = new HashMap<>();
            flag = new int[num];

            for (int i = 0; i < num; i++) {
                int idx; //s.charAt(i)表示： i文件的前置是idx
                if ((idx = nums[i]) > 0) {
                    //下标对应的指向为正数，证明是存在前置节点的
                    //根据前置、后置关系更新邻接表
                    if (adj.containsKey(idx)) {
                        List<Integer> list = adj.get(idx);
                        list.add(i);
                        adj.put(idx, list);
                    } else {
                        List<Integer> list = new ArrayList<>();
                        list.add(i);
                        adj.put(idx, list);
                    }
                }
            }
            sb = new StringBuilder();
            for (int i = 0; i < num; i++) {
                if (!dfs(i)) return ""; //不存在该序列
            }

            //因为dfs的特性，导致到最终验证成功的那个节点开始插入字符，因此字符是反的
            sb = sb.reverse();

            //另一个问题：题目要求，若有多种答案，需要增序的那个
         
            return sb.toString();
        }

        public boolean dfs(int i) {
            if (flag[i] == -1) return true;
            else if (flag[i] == 1) return false;
            else {
                flag[i] = 1;
                
                List<Integer> posts = adj.get(i);
                boolean res = true;
                if (posts == null) {
                    flag[i] = -1;                   //kiziwa，dalenokodo，wadtasimokuowuku
                    sb.append(i); //这里也是成功的地方，别忘了！
                    return true;
                }
                for (int post: posts) {
                    res = res && dfs(post);
                    if (!res) return false;
                }
                flag[i] = -1;
                sb.append(i);//验证了之后，才能彻底添加这个位置到序列中
                return res;
            }
        }

        public static void main(String[] args) {
            Solution s = new Solution();
            String res = s.compileSeq("1, 2, -1,1");
            System.out.println(res);
        }


        StringBuilder res = new StringBuilder();
        public String compileSeq1 (String input) {
            int len;
            if (input == null || (len = input.length())== 0) return "";
            String[] numbers = input.split(",");
            len = numbers.length;
            int[] dic = new int[len];
            Set<Integer> cur = new HashSet<>();
            for (int i = 0; i < len; i++) {
                dic[i] = Integer.parseInt(numbers[i]);
            }
            
            while (cur.size() < len){
                for (int i = 0; i < len; i++) {
                if (dic[i] >= 0 && !cur.contains(dic[i])) {
                    dfs (i, dic, cur);
                } else {
                    if (cur.contains(i)) continue;
                    else {
                        cur.add(i);
                        res.append(i + ",");
                    }
                }
            }
        }
        res.deleteCharAt(res.length() - 1);
            // System.out.println(Arrays.toString(dic) + "  " + cur);
           
            return res.toString();
        }

        public void dfs(int idx, int[] dic, Set<Integer> cur) {
            if (dic[idx] == -1) {
                if (!cur.contains(idx)) {
                    res.append(idx + ",");
                }
                cur.add(idx);
                return;
            }
            dfs (dic[idx], dic, cur);
            if (!cur.contains(dic[idx])) {
                res.append(dic[idx] + ",");
                 cur.add(dic[idx]);
            }
        }

        
    }

    public static void main(String[] args) {
            Solution solution = new Solution();
            System.out.println(solution.compileSeq("5,0,4,4,5,-1"));
    }
}
